package main
import (
	"fmt"
	"time"
)
//快速排序算法 
//其算法时对冒泡排序的一种改进；
//基本思想： 通过一趟排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另一部分的所有数据都要小，
//			然后再按此方法对这两个部分数据分别进行快速排序，整个排序过程可以  递归  进行，以此达到整个数据变成有序序列。
func main(){
	var array [10]int = [...]int{11,2,42,21,4,64,14,50,91,16}
	fmt.Println(array)
	start := time.Now().UnixNano()
	QuickSort(0,len(array)-1,&array)
	end := time.Now().UnixNano()
	fmt.Println(array)
	fmt.Println("所用时间：",end - start)
}

//1、left表示 数组左边的下标
//2、right表示 数组右边的下标
//3、a为要排序的数组
func QuickSort(left int,right int,a *[10]int){
	l := left
	r := right
	//pivot 是中轴 然后左右分
	pivot := a[(left + right) / 2]

	//for 的目标是 将 比pivot小的数放在左边  比pivot大的数放在右边
	for ;l < r;{
		for ;a[l] < pivot;{
			l++
		}
		for ;a[r] > pivot;{
			r--
		}
		if l >= r{ //如果l 已经 大于 r 就结束循环
			break
		}
		//找到了 a[l]是比中轴大的，而a[r]是比中轴小的，所以要交换位置
		a[l],a[r] = a[r],a[l]
		if a[l] == pivot{
			r--
		}
		if a[r] == pivot{
			l++
		}
	}
	//如果l == r需要挪一下，方便递归免得死循环
	if l == r{
		l++
		r--
	}
	//到这一步的时候 中轴的左右已经达到了左边都是比中轴小的，右边都是比中轴大的，然后把左右两边再一次递归调用同一个函数
	//向左递归
	if left < r {
		QuickSort(left,r,a)
	}
	//向右递归
	if right > l {
		QuickSort(l,right,a)
	}
}

